package com.dyz.leetcode._20_dynamicProgramming._474;

public class findMaxForm01 {
    //二维多代价dp问题
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]  表示包含i个0和j个1的最大子集大小
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        for (int i = 0; i < strs.length; i++) {
            int[] counts = countzeroesones(strs[i]);
            int zeros = counts[0];
            int ones = counts[1];
            for (int zero = m; zero >= zeros; zero--) {
                for (int one = n; one >= ones ; one--) {
                    dp[zero][one] = Math.max(dp[zero][one], dp[zero-zeros][one-ones]+1);
                }
            }
        }
        return dp[m][n];

    }
    private int[] countzeroesones(String s){
        int[] c = new int[2];

        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i)-'0']++;
        }
        return c;
    }
}
